﻿//#include <iostream>
//#include <queue>
//using namespace std;
//queue<int> myQe;
//queue<int> myQA[10];整数队列对象数组 myQA[0]第一个队列
//int rear = 0;
//int front = 0;
//int push(int item)
//{
//    if (rear == 10)
//    {
//        return -1;
//    }
//    else
//    {
//        myQA[rear].push( item);
//        rear++;
//        return 1;
//    }
//}
//bool empty()
//{
//    if (rear == front)
//    {
//        return true;
//    }
//    else
//    {
//        return false;
//    }
//}
//int pop()
//{
//    if (!empty())
//    {
//        int temp = myQA[front].front();
//        myQA[front].pop();移除front队列
//        front++;
//        return temp;
//    }
//    else
//        return -1;
//}
//
//int main()
//{
//    int n,itemp;
//    cin >> n;
//    char *arr = new char[n];
//    for (int i = 0; i < n; i++)
//    {
//        cin >> arr[i];
//    }
//    for (int j = 0; j < n; j++)
//    {
//        cin >> itemp;
//        myQe.push(itemp);
//    }
//    int sum1 = 0, sum2 = 0, sum3 = 0;
//    int n1 = 0, n2 = 0, n3 = 0;
//    for (int i = 0; i < n; i++)
//    {
//        itemp = myQe.front();
//        myQe.pop();
//        if (arr[i] == 'A')
//        {
//            n1++;
//            sum1=sum1+ itemp;
//        }
//        else if (arr[i] == 'B')
//        {
//            n2++;
//            sum2 = sum2 + itemp;
//        }
//        else
//        {
//            n3++;
//            sum3 = sum3 + itemp;
//        }
//    }
//    cout << (int)sum1 / n1 << endl;
//    cout << (int)sum2 / n2 << endl;
//    cout << (int)sum3 / n3<< endl;
//    return 0;
//}
//#include <iostream>
//#include <queue>
//#include <stack>
//using namespace std;
//queue<int> myQe;
//queue<int> myQA[10];
//int rear = 0;
//int front = 0;
//typedef struct// 创建一个结构体
//{
//    int top;
//    int size;
//    int* data;
//}Sqstack;
//void init(Sqstack& s, int len)//初始化
//{
//    s.size = len;
//    s.top = -1;
//    s.data = new int[len];
//}
//int Push(Sqstack& s, int data1)//进栈操作
//{
//    if (s.top == s.size - 1)//判断栈是否已满
//    {
//        return -1;
//    }
//    else
//    {
//        s.top++;
//        s.data[s.top] = data1;
//        return 1;
//    }
//}
//int Pop(Sqstack& s)//出栈操作（从后往前）
//{
//    if (s.top == -1)//判断是否为空栈
//    {
//        return -1;
//    }
//    else
//    {
//       int c = s.data[s.top];
//        s.top--;
//        return c;
//    }
//}
//int push(int item)
//{
//    if (rear == 10)
//    {
//        return -1;
//    }
//    else
//    {
//        myQA[rear].push( item);
//        rear++;
//        return 1;
//    }
//}
//bool empty()
//{
//    if (rear == front)
//    {
//        return true;
//    }
//    else
//    {
//        return false;
//    }
//}
//int pop()
//{
//    if (!empty())
//    {
//        int temp = myQA[front].front();
//        myQA[front].pop();
//        front++;
//        return temp;
//    }
//    else
//        return -1;
//}
//int main()
//{
//    int t,k,m;
//    double n;
//    cin >> t;
//    char arr[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };
//    for (int i = 0; i < t;i++)
//    {
//        int len1 = 0;
//        cin >> n >> k;
//        m = (int)n;
//        if (m == 0)
//        {
//            cout << "0";
//        }
//        else
//        {
//            Sqstack s;
//            init(s, 1000);
//            while (m != 0)
//            {
//                Push(s, m % k);
//                len1++;
//                m = m / k;
//            }
//            for (int j = 0; j < len1; j++)
//            {
//                int p = Pop(s);
//                if ( p > 9)
//                {
//                    cout << arr[p - 10];
//                }
//                else
//                    cout << p;
//            }
//            cout << ".";
//            n = n - (int)n;
//            for (int j = 0; j < 3; j++)
//            {
//                n = n * k;
//                myQe.push((int)n);
//                n = n - (int)n;
//            }
//            for (int j = 0; j < 3; j++)
//            {
//                m = myQe.front();
//                myQe.pop();
//                if ( m > 9)
//                {
//                    cout << arr[m - 10];
//                }
//                else
//                    cout << m;
//            }
//        }
//        cout << endl;
//    }
//    return 0;
//}
//#include <iostream>
//#include <queue>
//#include <string>
//using namespace std;
//queue<int> myQe;
//queue<int> myQA[10];
//queue<int> order;
//int rear = 0;
//int front = 0;
//int arr1[100000];
//bool arr2[10] = { false };
//int push(int item)
//{
//    int a = arr1[item];
//    if (arr2[a])
//    {
//        myQA[a].push(item);//加入组末尾
//    }
//    else
//    {
//        myQA[a].push(item);
//        order.push(a);
//        arr2[a] = true;
//        rear++;
//    }
//    return 1;
//}
//bool empty()
//{
//    if (rear == front)
//    {
//        return true;
//    }
//    else
//    {
//        return false;
//    }
//}
//int pop()
//{
//    if (!empty())
//    {
//        int temp1 = order.front();
//        int temp2 = myQA[temp1].front();
//        myQA[temp1].pop();   
//        if (myQA[temp1].empty()) 
//        {
//            order.pop();
//            arr2[temp1] = false;
//            front++;
//        }
//        return temp2;
//    }
//    else
//        return -1;
//}
//int main()
//{
//    int t,n,max=0;
//    string str;
//    cin >> t;
//    for (int i = 0; i < t; i++)
//    {
//        cin >> n;
//        int* arr = new int[n];
//        for (int j = 0; j < n; j++)
//        {
//            cin>> arr[j];
//            arr1[arr[j]] = i;
//        }
//        delete[]arr;
//    }
//    ;
//    int m;
//    while (cin>> str)
//    {
//        if (str == "ENQUEUE")
//        {
//            cin >> m;
//            push(m);
//        }
//        else if (str == "DEQUEUE")
//        {
//            int t = pop();
//            if (t != -1)
//            {
//                cout << t << " ";
//            }
//        }
//        else
//        {
//            break;
//        }
//    }
//    return 0;
//}
//#include <iostream>
//#include <queue>
//#include <string>
//#include <iomanip>
//using namespace std;
//struct Customer {
//    int a=0; 
//    int w=0;
//    int c=0;
//    int wait=0;
//    int flag = 0;
//};
//int main()
//{
//    queue< Customer> myQe;
//    int  n;
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        Customer  customer;
//        cin >> customer.a >> customer.w;
//        myQe.push(customer);
//    }
//    int m;
//    cin >> m;
//    queue<Customer>* w = new queue<Customer>[m];
//    for (int j = 0; j < m; j++)
//    {
//        Customer customer1;
//        w[j].push(customer1);
//    }
//    queue<Customer> comp;
//    while (!myQe.empty())
//    {
//        int min = 1000;
//        for (int i = 0; i < m; i++)
//        {
//            if (!w[i].empty())
//            {
//                if (min > w[i].front().c)
//                {
//                    min = w[i].front().c;
//                }
//            }
//        }
//        for (int i = 0; i < m; i++)
//        {
//            if (!w[i].empty() && min == w[i].front().c)
//            {
//                int sparetime = w[i].front().c;
//                w[i].push(myQe.front());
//                comp.push(w[i].front());
//                w[i].pop();
//                myQe.pop();
//                if (w[i].front().a < sparetime)
//                {
//                    w[i].front().wait = sparetime - w[i].front().a;
//                    w[i].front().flag = 1;
//                    w[i].front().c = sparetime + w[i].front().w;
//                }
//                else if (w[i].front().a >= sparetime)
//                {
//                    sparetime = w[i].front().a;
//                    w[i].front().c = sparetime + w[i].front().w;
//                }
//                break;
//            }
//        }
//    }
//    int max = 0;
//    for (int i = 0; i < m; i++)
//    {
//        if (!w[i].empty())
//        {
//            if (max < w[i].front().c)
//            {
//                max = w[i].front().c;
//            }
//        }
//    }
//    int mwait = 0;
//    double average = 0;
//    queue<Customer> temp = comp;
//    while (!temp.empty())
//    {
//        if (temp.front().flag == 1)
//        {
//            average += temp.front().wait;
//            if (mwait < temp.front().wait)
//            {
//                mwait = temp.front().wait;
//            }
//        }
//        temp.pop();
//    }
//    for (int i = 0; i < m; i++)
//    {
//        if (!w[i].empty() && w[i].front().flag == 1)
//        {
//            average += w[i].front().wait;
//            if (mwait < w[i].front().wait)
//            {
//                mwait = w[i].front().wait;
//            }
//        }
//    }
//    cout << fixed << setprecision(1) << average / n << " ";
//    cout << mwait << " " << max << endl;
//    delete[] w;
//    return 0;
//}
#include<iostream>
#include <queue>
using namespace std;

class AnimalShelf
{
public:
    queue<int> cat;
    queue<int> dog;
    AnimalShelf() {}
    void enqueue()
    {
        int num;
        string type;
        cin >> num>> type;
        if (type == "cat")
            cat.push(num);
        else
            dog.push(num);
    }
    void dequeueAny()
    {
        if (cat.empty() && dog.empty())
        {
            cout << "[-1 none] ";
            return;
        }
        if (cat.empty())
        {
            cout << "[" << dog.front() << " dog] ";
            dog.pop();
            return;
        }
        if (dog.empty())
        {
            cout << "[" << cat.front() << " cat] ";
            cat.pop();
            return;
        }
        if (cat.front() < dog.front())
        {
            cout << "[" << cat.front() << " cat] ";
            cat.pop();
            return;
        }
        else
        {
            cout << "[" << dog.front() << " dog] ";
            dog.pop();
            return;
        }
    }
    int dequeueDog()
    {
        if (dog.empty())
        {
            cout << "[-1 none] ";
            return 1;
        }
        else
        {
            cout << "[" << dog.front() << " dog] ";
            dog.pop();
            return 0;
        }
    }
    int dequeueCat()
    {
        if (cat.empty())
        {
            cout << "[-1 none] ";
            return 0;
        }
        else
        {
            cout << "[" << cat.front() << " cat] ";
            cat.pop();
            return 0;
        }
    }
};

int main()
{
    int t, n;
    string op;
    cin >> t;
    for(int i=0;i<t;i++)
    {
        AnimalShelf animal;
        cin >> n;
        while (n--)
        {
            cin >> op;
            if (op == "enqueue")
            {
                animal.enqueue();
            }
            if (op == "dequeueAny")
            {
                animal.dequeueAny();
            }
            if (op == "dequeueCat")
            {
                animal.dequeueCat();
            }
            if (op == "dequeueDog")
            {
                animal.dequeueDog();
            }
        }
        cout << endl;
    }
}